/* ***************************************************************************************
 *  In dijkstra's program we
 *  Filling the matrix by creat to 3 arrays with size of number of edges first
 *		 array for All source vertex second array for All distenation vertex array third for
 * 	 edge cost of same index isource & destination  then by way join them into matrix
 *
 *
 * ***************************************************************************************/
#include<iostream.h>
class dijkstra
{
private:
 int graph[15][15];
 int set[15],predecessor[15],mark[15],pathestimate[15];
 int source;
 int num_of_vertices;
int num_of_edges;
  int v1[15],v2[15],edge[15];

public:
 int minimum();
 void read();
 void initialize();
 void printpath(int);
 void algorithm();
 void output();
};


void dijkstra::read(){
/////////////  Read from user ////////////////
  cout<<"\n enter the number of vertices: ";
  cin>>num_of_vertices;
  // valid num_of_vertices
  while(num_of_vertices<=0){
	cout<<"\nthis is meaningless,enter the number carefully";
	cin>>num_of_vertices;
  }
  cout<<"\nEnter number of edges: ";
  cin>>num_of_edges;
  // valid num_of_edges
  while(num_of_edges<=0){
	cout<<"\nthis is meaningless,enter the number carefully\n";
	cin>>num_of_edges;
  }
  cout<<"\nTo get (v1,v2)= adjacent Enter  v1 then v2 then adjacent:\n ";
  for(int i=1;i<=num_of_edges;i++){
	 cout<<"\nEdge["<<i<<"]= ";
		cin>>v1[i];
		cin>>v2[i];
		cin>>edge[i];

  }

  for( i=1;i<=num_of_vertices;i++){
	int check=0;
	for(int j=1;j<=num_of_vertices;j++){
	  if(i==j)
		graph[i][j]=0;
	  else{
		 for(int e=1;e<=num_of_edges;e++)
		  if((v1[e]==i && v2[e]==j) || (v1[e]==j && v2[e]==i)){
			 graph[i][j]=edge[e];
			 check=1;
			}
		  if(check==0)
			 graph[i][j]=-1;
		 }
	 }
  }//for !!!!!!!!!!!

///////////  Print Matrix ///////////////////////
	 cout<<"\n\n";
	 for( i=1;i<=num_of_vertices;i++)
	  cout<<"\t"<<i;
	 cout<<"\n";
	 for( i=1;i<=num_of_vertices;i++)
	  cout<<"\t__";
	 cout<<"\n\n";
	 for( i=1;i<=num_of_vertices;i++){
	  cout<<i<<"|\t";
	  for(int j=1;j<=num_of_vertices;j++){
		cout<<graph[i][j];
		cout<<"\t";
	  }
	  cout<<"\n\n";
	}
/////////////////////////////////




cout<<"\nenter the source vertex\n";
cin>>source;




}//end read

void dijkstra::initialize()
{
 for(int i=1;i<=num_of_vertices;i++)
 {
  mark[i]=0;
  pathestimate[i]=999;
  predecessor[i]=0;
 }
 pathestimate[source]=0;
}
void dijkstra::algorithm()
{
 initialize();
 int count=0;
 int i;
 int u;
while(count<num_of_vertices)
 {
  u=minimum();
  set[++count]=u;
  mark[u]=1;
  for(i=1;i<=num_of_vertices;i++)
  {
	if(graph[u][i]>0)
	{
	 if(mark[i]!=1)
	 {
	 if(pathestimate[i]>pathestimate[u]+graph[u][i])
	 {
	  pathestimate[i]=pathestimate[u]+graph[u][i];
	  predecessor[i]=u;
	 }
	 }
	}
  }
 }

}

void dijkstra::printpath(int i)
{
cout<<endl;
if(i==source)
{
cout<<source;
}
else if(predecessor[i]==0)
cout<<"no path from "<<source<<" to "<<i;
else
{
printpath(predecessor[i]);
cout<<".."<<i;
}
}
void dijkstra::output()
{
 for(int i=1;i<=num_of_vertices;i++)
 {
 printpath(i);
 if(pathestimate[i]!=999)

  cout<<"->("<<pathestimate[i]<<")\n";
 }
 cout<<endl;
}





int dijkstra::minimum()
{
int min=999;
 int i,t;
 for(i=1;i<=num_of_vertices;i++)
 {
  if(mark[i]!=1)
  {
	if(min>=pathestimate[i])
	{
	min=pathestimate[i];
	t=i;
	}
  }
 }
 return t;
}
void main()
{
cout<<"\tWelcome to Dijkstra's algorithm . . ! !\n";


 dijkstra s;
 s.read();
 s.algorithm();
 s.output();
}
